package mao.algorithm.redbook.demo;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class NineTailModel {
	//T:1,H:0
	private static int NUMBER_OF_NODE = 512;
	private List<List<Edge>> edges = new ArrayList<>();

	public NineTailModel() {
		getEdges();
	}

	public  Tree bfs(char[] root) {
		int[] parent = new int[NUMBER_OF_NODE];
		boolean[] isVisited = new boolean[512];
		for (int i = 0;i<NUMBER_OF_NODE;i++) {
			isVisited[i] = false;
		}
		
		int indexOfRoot = getIndex(root);
		
		Queue<Integer> queue = new LinkedList<Integer>();
		
		queue.offer(indexOfRoot);
		parent[indexOfRoot]=-1;
		isVisited[indexOfRoot]=true;
		
		while(!queue.isEmpty()){
			Integer currentNode = queue.poll();
			List<Edge> list = edges.get(currentNode);
			for(int i=0;i<list.size();i++){
				int childIndex = list.get(i).getV();
				if(isVisited[childIndex] == false){
					parent[childIndex] = currentNode;
					isVisited[childIndex] = true; 
					queue.offer(childIndex);
				}
			}
		}
		
		Tree tree = new Tree(parent);
		return tree;
		
	}

	private void getEdges() {
		for(int u = 0;u<NUMBER_OF_NODE;u++){
			edges.add(new ArrayList<Edge>());
			char[] node = getNode(u);
			for(int j = 0;j<9;j++){
				if(node[j] == 'H'){
				  int v = filp(node,j); //这里J 不小心写成U 造成错误。
				  edges.get(u).add(new Edge(u,v));
				}
			}
		}
	}

	private int filp(char[] arr, int i) {
		int row = i/3;
		int column = i%3;
		char[] node = arr.clone();
		
		fiipACell(node,row-1,column);
		fiipACell(node,row+1,column);
		fiipACell(node,row,column);
		fiipACell(node,row,column-1);
		fiipACell(node,row,column+1);
		
		int v = getIndex(node);
		
		return v;
	}

	

	private void fiipACell(char[] node, int row, int column) {
		if( row >= 0 && row <3 && column >= 0 && column <3){
			if( node[row*3+column] == 'H'){
				node[row*3+column] = 'T';
			}else{
				node[row*3+column] = 'H';
			}
		}
		
	}

	public static char[] getNode(int index) {
		char[] arr = new char[9];
		for(int i = 8 ;i>=0;i--){
			if(index%2 == 1){
				arr[i] = 'T';
			}
			else{
				arr[i] = 'H';
			}
			index/=2;
		}
		return arr;
	}
	
	public static void showNode(char [] node){
		System.out.println("**********");
		for (int i=0;i<node.length;i++) {
			if(i%3 == 0){
				System.out.println("");
			}
			System.out.print(node[i]);
			
		}
	}
	public static int getIndex(char[] node) {
		int index=0;
		for(int i=0;i<9;i++){
			if(node[i] == 'T'){
				index = index*2+1;
			}else{
				index = index*2+0;
			}
		}
		return index;
	}
	
	public static class Tree{
		int[] parent = new int[NUMBER_OF_NODE];

		public Tree(int[] parent) {
			this.parent = parent.clone();
		}
		
		public List<Integer> getShortPath(int index){
			ArrayList<Integer> path = new ArrayList<Integer>();
			while(parent[index] != -1){
				path.add(index);
				index=parent[index];
			}
			path.add(index);
			return path;
		}
		
		public List<Integer> getShortPath(char[] node) {
			int index = NineTailModel.getIndex(node);
			List<Integer> path = getShortPath(index);
			return path;
		}
		
		public void getShortPathAndShow(int index){
			List<Integer> path = getShortPath(index);
			for(int i=path.size()-1;i>=0;i--){
				char[] node = NineTailModel.getNode(path.get(i));
				NineTailModel.showNode(node);
			}
		}
		
		public void getShortPathAndShow(char[] node){
			int index = NineTailModel.getIndex(node);
			List<Integer> path = getShortPath(index);
			for(int i=path.size()-1;i>=0;i--){
				char[] node1 = NineTailModel.getNode(path.get(i));
				NineTailModel.showNode(node1);
			}
		}
	}
	
}
